package  main.java.leetcode.editor.cn;
//2023-05-14 21:24:36
//在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。 
//
// 请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：barcodes = [1,1,1,2,2,2]
//输出：[2,1,2,1,2,1]
// 
//
// 示例 2： 
//
// 
//输入：barcodes = [1,1,1,1,2,2,3,3]
//输出：[1,3,1,3,2,1,2,1] 
//
// 
//
// 提示： 
//
// 
// 1 <= barcodes.length <= 10000 
// 1 <= barcodes[i] <= 10000 
// 
// Related Topics 贪心 数组 哈希表 计数 排序 堆（优先队列） 👍 157 👎 0

import java.util.*;

class DistantBarcodes {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new DistantBarcodes().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer,Integer> count = new HashMap<>();
        for(int barcode : barcodes){
            count.put(barcode,count.getOrDefault(barcode,0)+1);
        }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0]-o1[0];
            }
        });
        for(Map.Entry<Integer,Integer> entry : count.entrySet()){
            priorityQueue.offer(new int[]{entry.getValue(),entry.getKey()});
        }

        int n = barcodes.length;
        int[] ans = new int[n];

        for(int i = 0;i<n;i++){
            int[] p = priorityQueue.poll();
            int cx = p[0];
            int x = p[1];
            if(i == 0 || ans[i-1] != x){
                ans[i] = x;
                if(cx > 1){
                    priorityQueue.offer(new int[]{cx-1,x});
                }
            }else {
                int[] p2 = priorityQueue.poll();
                int cy = p2[0];
                int y = p2[1];
                ans[i] = y;
                if(cy > 1){
                    priorityQueue.offer(new int[]{cy-1,y});
                }
                priorityQueue.offer(new int[]{cx,x});
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
